//
//  Problem169.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/12.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 169. 多数元素
 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 示例 1：
     输入：nums = [3,2,3]
     输出：3
 
 示例 2：
    输入：nums = [2,2,1,1,1,2,2]
    输出：2
  
 提示：
 n == nums.length
 1 <= n <= 5 * 104
 -109 <= nums[i] <= 109
  
 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 */
class Problem169: NSObject {

    /*
     ProblemMS1710 摩尔投票法:
      1: 提供一个计数器n=1，提供一个value = nums[0]
      2: 遍历数组，对比num[i]是否和value相等，相等n+=1，不想等n-=1，如果n=0，那么让value=nums[i]
      3: 如果有主要元素，那么n一定是大于0，因为主要元素个数和大于其他元素的个数和，最坏的情况都是count等于1，例如：[1,2,3,2,4,2,5,2,2]，那么最后的一个2是不会被抵消的。
      4: 如果没有主要元素，那么count还是有可能大于0的，因为就怕有几个重复的元素在最后面，且前面的count是小于最后这个重复的数的个数的，例如：[1,2,3,4,5,6,7,7,7,7] n=4,
      所以当我们遍历完之后，需要判断count是否大于1，大于1之后temp也不一定是主要元素，所以还需要一次遍历，判断这个数的重复次数是否大于数组的一半
      本题中“给定的数组总是存在多数元素”, 所以第4步不用考虑
     */
    
    func majorityElement(_ nums: [Int]) -> Int {
        var n = 1
        var target = nums[0]
        
        for i in (1 ..< nums.count) {
            if target == nums[i] {
                n += 1
            } else {
                n -= 1
            }
            if n == 0 {
                target = nums[i+1]
            }
        }
        
        return target
    }
}
